JS排序算法：冒泡、选择、插入、归并、快速、希尔、堆、计数

2022-12-25 23:25| 来源: 网络整理| 查看: 265

1. 冒泡排序算法实现（JAVAscript）

//冒泡排序算法(JavaScript) //author：Hengda //arr数组 //mode false 升序 ture 降序 function bubbleSort( arr, mode ){ var i, j, temp, len = arr.length; for( i = len - 1 ; i > 0; i-- ){ for( j = 0; j < i; j++ ){ if( mode ? arr[ j + 1 ] < arr[ j ] : arr[ j + 1 ] > arr[ j ] ){ temp = arr[ j + 1 ]; arr[ j + 1 ] = arr[ j ]; arr[ j ] = temp; } } } return arr; }

2. 计数排序算法实现（javascript）

//计数排序算法(javascript) //author：Hengda //arr数组 //mode false 升序 ture 降序 function countingSort( arr, mode ){ //i,j为控制变量，temp为交换变量，len为数组的长度 var i, j, temp, len = arr.length; var countArr = [];//用于原始数组中统计各元素出现的次数 var fillPos;//标记下一个回填位置 var countArrLen;//计数数组的长度 //统计 for( i = 0; i < len; i++ ){ if( countArr[ arr[ i ] ] != null ){ countArr[ arr[ i ] ] ++; }else{ countArr[ arr[ i ] ] = 1; } } //将数据重新排列回填到原始数组中 //统计 var fillPos = 0;//回填起始位置 var countArrLen = countArr.length; if( mode ){ // for( i = countArrLen - 1; i >=0; i-- ){ // if( countArr[ i ] != null ){ //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos for( j = 0; j < countArr[ i ]; j++ ){ arr[ fillPos++ ] = i; } } } }else{ // for( i = 0; i < countArrLen; i++ ){ // if( countArr[ i ] != null ){ //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos for( j = 0; j < countArr[ i ]; j++ ){ arr[ fillPos++ ] = i; } } } } //排序完成 return arr; }

3. 堆排序算法实现（javascript）

//功能：堆排序(javascript) //author： Hengda //arr：待排序数组 //mode： true 从大到小排序，false 从小到大排序 function heapSort( arr, mode ){ var len = arr.length; //数组的长度 var temp; //用于交换节点值 var endHeapNodeNo; //堆末尾节点在数组中的下标 //将数组调整为二叉堆 for( var i = Math.floor( len / 2 ) - 1; i >= 0; i-- ){ heapNodeSink( arr, i, len, mode ); } for( var heapLen = len; heapLen > 0; heapLen-- ){ endHeapNodeNo = heapLen - 1;//堆的最后一个节点的序号 //交换堆顶和堆尾元素 temp = arr[ endHeapNodeNo ]; arr[ endHeapNodeNo ] = arr[ 0 ]; arr[ 0 ] = temp; //对除了堆尾元素组成的堆进行堆顶下沉操作 heapNodeSink( arr, 0, heapLen - 1, mode ); } return arr; } //堆中某节点按升序或者降序递归下沉 //author： Hengda //arr：待排序数组 //nodeNo：二叉树中指定节点的序号/堆数组中的下标 //heapLen：堆的长度 //mode： true 大的下沉，false 小的下沉 function heapNodeSink( arr, nodeNo, heapLen, mode ){ var leftChild = ( nodeNo + 1 ) * 2 - 1; //做孩子 var rightChild = leftChild + 1; //右孩子 var maxminNo = nodeNo; //最大值的序号 var temp; //用户变量值得交换 if( mode ){ // if( heapLen > leftChild && arr[ maxminNo ] > arr[ leftChild ] ){ maxminNo = leftChild;//更新最大节点序号 } if( heapLen > rightChild && arr[ maxminNo ] > arr[ rightChild ] ){ maxminNo = rightChild;//更新最大节点序号 } }else{ if( heapLen > leftChild && arr[ maxminNo ] < arr[ leftChild ] ){ maxminNo = leftChild;//更新最大节点序号 } if( heapLen > rightChild && arr[ maxminNo ] < arr[ rightChild ] ){ maxminNo = rightChild;//更新最大节点序号 } } //最大值所在节点有变化，则交换 if( maxminNo != nodeNo ){ //交换 temp = arr[ maxminNo ]; arr[ maxminNo ] = arr[ nodeNo ]; arr[ nodeNo ] = temp; //继续下沉操作 heapNodeSink( arr, maxminNo, heapLen, mode ); } }

4. 插入排序算法实现（javascript）

//插入排序算法(javascript) //算法原理 //author：Hengda //2020/1/25 //arr 待排序数组 //mode true 从大到小排列，false 从小到大排列 function insertionSort( arr, mode ){ var i, j, temp, len = arr.length;//len为待排序数组长度 temp为交换变量 i j为控制变量。 //从数组的第二个元素开始逐个往后处理。 for( i = 1; i < len; i++ ){ //将当前被处理元素值记录下来。 temp = arr[ i ]; //以下标倒序逐一比较当前元素位置之前的所有元素，如果比当前元素大，则逐一向后覆盖一个元素。 for( j = i - 1; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j-- ){ arr[ j + 1 ] = arr[ j ]; } //将点前被处理元素的值填入最终空缺的位置即（j + 1）注意这个 j 已经被for循环做了-1操作，所以这里需要+1。 arr[ j + 1 ] = temp; } //遍历完成后，整个数组即为有序数组。 return arr; }

5. 归并排序算法实现（javascript）

//归并排序算法(javascript) //author：Hengda //arr数组 //start 数组中待排序段落的起止位置，len为数据段的长度 //mode false 升序 ture 降序 function mergeSort( arr, start, len ,mode){ var i, j, temp; //计算左侧数据段的位置和长度 var lstart = start; var llen = Math.floor( len / 2 ); //计算右侧数据段的位置和长度 var rstart = lstart + llen; var rlen = len - llen; //分别对左右分段进行进行插入排序 if( llen > 4 ) mergeSort( arr, lstart, llen ); if( rlen > 4 ) mergeSort( arr, rstart, rlen ); //对当前数据段进行插入排序 for( i = start + 1; i < len + start; i++ ){ temp = arr[ i ]; for( j = i - 1; j >= start && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j-- ){ arr[ j + 1 ] = arr[ j ]; } arr[ j + 1 ] = temp; } return arr; }

6. 选择排序算法实现（javascript）

//选择排序算法(javascript) //author：Hengda //arr数组 //mode false 升序 ture 降序 function selectionSort( arr, mode ){ //i,j为控制变量，miniMaxNo为标记发现的最大或者最小元素的下标，temp为交换变量，len为数组的长度 var i, j, minMaxNo, temp, len = arr.length; // for( i = 0; i < len; i++ ){ //当前位置初始为最小或最大数的位置 minMaxNo = i; //遍历后续所有元素与minMaxNo对应的元素做比较，如果比minMaxNo大或者小，则更新minMaxNo的值为新元素的下标 for( j = i; j < len; j++ ){ if( mode ? arr[ j ] > arr[ minMaxNo ] : arr[ j ] < arr[ minMaxNo ] ){ minMaxNo = j; } } //将最终确定的最大或者最小值与当前被处理位置i对应的元素值做交换 temp = arr[ minMaxNo ]; arr[ minMaxNo ] = arr[ i ]; arr[ i ] = temp; } //排序完成 return arr; }

7. 希尔排序算法实现（javascript）

//希尔排序算法(javascript) //author：Hengda //arr数组 //mode false 升序 ture 降序 function shellSort( arr, mode ){ //1,j,k为控制变量，gap为分组间隙初始化为1，temp用于交换数据，len数组的长度 var i, j, k, gap = 1, temp, len = arr.length; //计算合适的分组元素间隙，这里计算得到gap的最大值，这里的5也可以是其他数，值不同，实际排序速度也不同 while( gap< len / 5 ){ gap = gap*5 + 1; } //开始排序 while( gap > 0 ){ //以下按分组排序，该排序原理为插入排序，如看不明白，可参考插入排序算法逻辑 for( i = gap; i < len; i++ ){ temp = arr[ i ]; for( j = i - gap; j >= 0 && ( mode ? arr[ j ] < temp : arr[ j ] > temp ); j -= gap ){ arr[ j + gap ] = arr[ j ]; } arr[ j + gap ] = temp; } //缩小分组间隔值 gap = Math.floor( gap / 5 ); } return arr; }

8. 快速排序算法实现（javascript）

//快速排序(javascript) //author：Hengda //arr数组 //start 待排序数据段的起始下标（含） //end 待排序数据段终止下标（含） //mode false 升序 ture 降序 function quickSort( arr, start, end, mode ){ var i,j,temp; var divValue; if( start < end ){ //初始化基准值 baseValue = arr[ end ]; j = start; //遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序） for( i = start; i = baseValue : arr[ i ] start ) quickSort( arr, start, j - 1, mode ); if( j < end ) quickSort( arr, j + 1, end, mode ); } return arr; }

9. 测试排序1万个无序数，耗时如下

//测试排序10000个数 testSort( 10000, false ); ``` ```javascript jssort.html:388 正在生成 10000个无序数... jssort.html:392 生成 10000个无序数完成 jssort.html:344 --------- jssort.html:346 快速排序： jssort.html:358 -正序耗时：: 22.447265625ms jssort.html:372 -倒序耗时：: 7.83203125ms jssort.html:344 --------- jssort.html:346 希尔排序： jssort.html:358 -正序耗时：: 7.2939453125ms jssort.html:372 -倒序耗时：: 5.231689453125ms jssort.html:344 --------- jssort.html:346 计数排序： jssort.html:358 -正序耗时：: 7.36083984375ms jssort.html:372 -倒序耗时：: 7.77392578125ms jssort.html:344 --------- jssort.html:346 插入排序： jssort.html:358 -正序耗时：: 9.529052734375ms jssort.html:372 -倒序耗时：: 9.830078125ms jssort.html:344 --------- jssort.html:346 堆排序： jssort.html:358 -正序耗时：: 8.35107421875ms jssort.html:372 -倒序耗时：: 2.64990234375ms jssort.html:344 --------- jssort.html:346 归并排序： jssort.html:358 -正序耗时：: 82.681884765625ms jssort.html:372 -倒序耗时：: 114.632080078125ms jssort.html:344 --------- jssort.html:346 选择排序： jssort.html:358 -正序耗时：: 96.762939453125ms jssort.html:372 -倒序耗时：: 151.841064453125ms jssort.html:344 --------- jssort.html:346 冒泡排序： jssort.html:358 -正序耗时：: 252.561767578125ms jssort.html:372 -倒序耗时：: 289.15087890625ms

10. 测试排序10万个无序数，耗时结果如下

//测试排序100000个数 testSort( 100000, false ); ``` ```javascript testSort(100000) jssort.html:386 --------- jssort.html:388 正在生成 100000个无序数... jssort.html:392 生成 100000个无序数完成 jssort.html:344 --------- jssort.html:346 快速排序： jssort.html:358 -正序耗时：: 10.38818359375ms jssort.html:372 -倒序耗时：: 11.48193359375ms jssort.html:344 --------- jssort.html:346 希尔排序： jssort.html:358 -正序耗时：: 22.110107421875ms jssort.html:372 -倒序耗时：: 19.762939453125ms jssort.html:344 --------- jssort.html:346 计数排序： jssort.html:358 -正序耗时：: 17.098876953125ms jssort.html:372 -倒序耗时：: 14.27294921875ms jssort.html:344 --------- jssort.html:346 插入排序： jssort.html:358 -正序耗时：: 25.2509765625ms jssort.html:372 -倒序耗时：: 27.105712890625ms jssort.html:344 --------- jssort.html:346 堆排序： jssort.html:358 -正序耗时：: 24.9130859375ms jssort.html:372 -倒序耗时：: 26.115966796875ms jssort.html:344 --------- jssort.html:346 归并排序： jssort.html:358 -正序耗时：: 4676.212158203125ms jssort.html:372 -倒序耗时：: 7991.64599609375ms jssort.html:344 --------- jssort.html:346 选择排序： jssort.html:358 -正序耗时：: 5662.914794921875ms jssort.html:372 -倒序耗时：: 12556.882080078125ms jssort.html:344 --------- jssort.html:346 冒泡排序： jssort.html:358 -正序耗时：: 21762.098876953125ms jssort.html:372 -倒序耗时：: 23281.131103515625ms

以下是测试函数

//测试排序算法函数 //totalNum 测试排序的元素个数 //isPrintArrData 是否打印数组数据 function testSort( totalNum, isPrintArrData ){ //生成测试数据 arr = makeData( totalNum, isPrintArrData ); //1>调用测试函数，对快速排序算法进行测试 TestOneSortFunc( arr, 'quickSort', ", 0, arr.length - 1" , "快速排序", isPrintArrData ); //2>调用测试函数，对希尔排序算法进行测试 TestOneSortFunc( arr, 'shellSort', "", "希尔排序", isPrintArrData ); //3>调用测试函数，对计数排序算法进行测试 TestOneSortFunc( arr, 'countingSort', "", "计数排序", isPrintArrData ); //4>调用测试函数，对插入排序算法进行测试 TestOneSortFunc( arr, 'heapSort', "", "插入排序", isPrintArrData ); //5>调用测试函数，对堆排序算法进行测试 TestOneSortFunc( arr, 'heapSort', "", "堆排序", isPrintArrData ); //6>调用测试函数，对归并排序算法进行测试 TestOneSortFunc( arr, 'mergeSort', ",0, arr.length", "归并排序", isPrintArrData ); //7>调用测试函数，对选择排序算法进行测试 TestOneSortFunc( arr, 'selectionSort', "", "选择排序", isPrintArrData ); //8>调用测试函数，对冒泡排序算法进行测试 TestOneSortFunc( arr, 'bubbleSort', "", "冒泡排序", isPrintArrData ); } //测试一个排序算法函数 function TestOneSortFunc( arr, funcName, funcOtherArgv, textName, isPrintArrData ){ console.log( "---------" ); //arr = makeData( totalNum ); console.log( textName + "：" ); //console.log( "原始数据：" ); //console.log( arr ); //正序 arr1 = arr.slice(); console.time( "-正序耗时：" ); //eval( funcName + "(arr1, 0, arr1.length - 1, false)" ); //, 0, arr1.length - 1 eval( funcName + "(arr1"+ funcOtherArgv +", false)" ); console.timeEnd( "-正序耗时：" ); if( isPrintArrData ){ console.log( "正序排序结果：" ); console.log( arr1 ); } //逆序 arr2 = arr.slice(); console.time( "-倒序耗时：" ); //eval( funcName + "(arr2, 0, arr2.length - 1, true)" ); //, 0, arr2.length - 1 eval( funcName + "(arr2"+ funcOtherArgv +", true)" ); console.timeEnd( "-倒序耗时：" ); if( isPrintArrData ){ console.log( "倒序排序结果：" ); console.log( arr2 ); } } //数据生成函数 function makeData( totalNum, isPrintArrData ){ var arr = []; var i = totalNum; console.log( "---------" ); console.log( "正在生成 " + totalNum + "个无序数..." ); while( i-- ){ arr.push( Math.floor( Math.random() * totalNum ) ); } console.log( "生成 " + totalNum + "个无序数完成" ); if( isPrintArrData ){ console.log( "原始无序数据：" ); console.log( arr ); } return arr; }

如果需要打印每个算法的排序结果，把 testSort() 的第二个参数设置为true即可

【本文地址】

公司简介

联系我们